package problem;

import javafx.util.Pair;

import java.util.LinkedList;

public class S_111 {
    //二叉树的最小深度
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //1.递归
    class Solution {
        public int minDepth(TreeNode root) {
            if(root==null) return 0;
            if(root.left==null&&root.right==null) return 1;
            if(root.left==null) return minDepth(root.right)+1;
            if(root.right==null) return minDepth(root.left)+1;
            int left=minDepth(root.left);
            int right=minDepth(root.right);
            return Math.min(left,right)+1;
        }
    }

    //2.栈DFS
    class Solution1{
        public int minDepth(TreeNode root) {
            LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
            if (root == null) {
                return 0;
            }
            else {
                stack.add(new Pair(root, 1));
            }

            int min_depth = Integer.MAX_VALUE;
            while (!stack.isEmpty()) {
                Pair<TreeNode, Integer> current = stack.pollLast();
                root = current.getKey();
                int current_depth = current.getValue();
                if ((root.left == null) && (root.right == null)) {
                    min_depth = Math.min(min_depth, current_depth);
                }
                if (root.left != null) {
                    stack.add(new Pair(root.left, current_depth + 1));
                }
                if (root.right != null) {
                    stack.add(new Pair(root.right, current_depth + 1));
                }
            }
            return min_depth;
        }
    }

    //3.队列BFS
    class Solution2 {
        public int minDepth(TreeNode root) {
            LinkedList<Pair<TreeNode, Integer>> queue = new LinkedList<>();
            if (root == null) {
                return 0;
            }
            else {
                queue.add(new Pair(root, 1));
            }

            int current_depth = 0;
            while (!queue.isEmpty()) {
                Pair<TreeNode, Integer> current = queue.poll();
                root = current.getKey();
                current_depth = current.getValue();
                if ((root.left == null) && (root.right == null)) {
                    break;
                }
                if (root.left != null) {
                    queue.add(new Pair(root.left, current_depth + 1));
                }
                if (root.right != null) {
                    queue.add(new Pair(root.right, current_depth + 1));
                }
            }
            return current_depth;
        }
    }
}
